#include<iostream>
#include<string>

#include<vector>



using namespace std;


const string s[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
vector<string> ret;
string path;

void dfs(string digits, int pos)
{
    if (pos == digits.size())
    {
        ret.push_back(path);
        return;
    }

    for (int i = 0; i < s[digits[pos] - '0'].size(); i++)
    {

        path += s[digits[pos] - '0'][i];
        dfs(digits, pos + 1);
        path.pop_back();
    }
}
vector<string> letterCombinations(string digits) {
    dfs(digits, 0);
    return ret;
}



int main()
{
	string s = "abc";
    letterCombinations("23");
	cout << s.size() << endl;
	return 0;
}

class Solution {
public:
    const string s[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0)
        {
            return ret;
        }
        dfs(digits, 0);
        return ret;
    }

    void dfs(string digits, int pos)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < s[digits[pos] - '0'].size(); i++)
        {

            path += s[digits[pos] - '0'][i];
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};